Construire un graphe non orienté avec des consignes - Corrigé

Énoncé

1. Est-il possible de construire un graphe non orienté à 5 sommets qui comporte deux sommets de degré 1, deux sommets de degré 2 et un sommet de degré 3 ? Si oui, le construire.

2. Est-il possible de construire un graphe non orienté à 5 sommets qui comporte deux sommets de degré 1, un sommet de degré 2 et deux sommets de degré 3 ? Si oui, le construire.

3. Est-il possible de construire un graphe simple non orienté à 5 sommets qui comporte deux sommets de degré 1, un sommet de degré 2 et deux sommets de degré 3 ? Si oui, construire un graphe qui répond à la consigne.

Solution 

1. La somme des degrés d'un tel graphe serait  \(2×1+2×2+3=9\) , qui est un nombre impair. Or, on a vu que la somme des degrés d'un graphe est égale au double du nombre d'arêtes, donc cette somme est un nombre pair, ainsi ce n'est pas possible.

2.    La somme des degrés d'un tel graphe serait  \(2×1+2+2×3=10\) , qui est un nombre pair, donc c'est envisageable. 
Essayons de concevoir un tel graphe.
Supposons que les deux sommets de degré 1 sont reliés entre eux, avec les autres sommets. On doit alors tracer un graphe d'ordre 3, qui compte deux sommets de degré 3 et un sommet de degré 2. 
D'où une première proposition avec un graphe qui n'est pas simple.

3. Proposition avec un graphe simple.